Geometric Structures: Problem Set E (Graph Theory - Euler Circuits and Chinese Postman Problem)

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk/

1. Can you draw a connected graph without loops and multiple edges whose degree sequence is:

6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 2, 1, 1

2. If p_k denotes the number of faces of a plane graph with k sides, can you draw a plane connected 3-valent graph with:

a.

p₃ = 2
p₄ = 2
p₅ = 2

b.

p₃ = 4
p₆ = 4


3. Can you draw a tree with the valences:

4, 3, 2, 2, 2, 1, 1, 1, 1, 1

Note: If the list above had 5 more 2's what would your answer be? Can you formulate a theorem based on this issue?

5. Write down two different Eulerian Circuits for the graphs below that start and end at A. (What is a reasonable definition for this concept of "different" Eulerian Circuits?)

-----------------------------------------------------------------------------

6. Write down two different Eulerian Circuits for the two graphs above that start and end at B.

7. If a graph G has an Eulerian Circuit that starts and ends at vertex v, explain why it also has an Eulerian Circuit that starts and ends at any of its vertices.

8. For the graph below, verify if the graph satisfies Euler's traversability theorem. (This refers to the theorem that tells when a graph has an Eulerian circuit.) How many vertices and edges does this graph have?

Note: There are some brief comments about the Chinese Postman Problem at the end.

9. Solve the Chinese postman problem (CPP) for the graph below starting at E. After you write down a solution, show how your solution also solves the CPP for the same graph starting at G. How many edges have to be repeated? What is the value of half the number of odd-valent vertices?

10. Repeat the problem above but for the same graph with weights. Here one wants to minimize total cost rather than number of repeated edges.

Sometimes it may be cheaper to repeat many edges of low cost rather than few edges of higher cost.

Chinese Postman Problem:

Given a connected graph with weights, find a tour of the edges that starts and ends at the same vertex, traverses each edge at least once, and for which the sum of the weights of the tour is as small as possible.

This problem is solvable in polynomial time using a complex algorithm developed by Jack Edmonds and Ellis Johnson. The algorithm involves finding a minimum weight matching (a disjoint collection of edges) in a general graph. However, small problems can be solved by trial and error methods. To solve such problems it is useful to have the shortest paths in the graph between vertices which are odd-valent. To find the shortest cost path between two vertices in a graph one can use Dijkstra's algorithm. This is the algorithm which is often used in conjunction with the hardware and software that is increasingly available in automobiles and which displays shortest time routes for driving between two locations.

It turns out that the Chinese Postman Problem for undirected graphs with weights and directed graphs (there is a line with an arrow on the edges) can be solved in polynomial time. Rather surprisingly, if the graph has some directed edges and some undirected edges (such graphs are called mixed graphs), the problem becomes NP-complete.